package midalgorithms.treeandmap;

import java.util.ArrayList;
import java.util.List;

public class _03BuildTree {
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        int len = preorder.length;
        //  将前序遍历和中序遍历的值放到list中
        //  目的：使用 indexOf() 和 remove() 和 subList() 方法
        List<Integer> preList = new ArrayList<>(len);
        List<Integer> midList = new ArrayList<>(len);
        for (int i = 0; i < preorder.length; i++) {
            preList.add(preorder[i]);
            midList.add(inorder[i]);
        }
        return buildHelper(preList,midList);
    }

    //  该递归算法的思想是只考虑当下每个结点的左右子树的遍历
    //  然后将该结点返回给上级即可！！！
    private static TreeNode buildHelper(List<Integer> preList, List<Integer> midList) {
        if (midList.size() == 0){
            return null;
        }
        //  前序遍历的第一个值就是根节点
        int rootVal = preList.remove(0);
        TreeNode root = new TreeNode(rootVal);
        //  取到根节点在中序遍历集合中的位置
        int mid = midList.indexOf(rootVal);
        root.left = buildHelper(preList,midList.subList(0,mid));
        root.right = buildHelper(preList,midList.subList(mid+1,midList.size()));
        return root;
    }
}
